package List$Stack$queue;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 有效括号判断
 */
public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairing = new HashMap<>(3);
        pairing.put('(', ')');
        pairing.put('{', '}');
        pairing.put('[', ']');
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
                continue;
            } else if (stack.empty()) return false;
            Character sTop = stack.pop();
            if (pairing.get(sTop) != c) return false;
        }
        return stack.empty();
    }

    public boolean isValidII(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
                continue;
            } else if (stack.empty()) return false;
            Character sTop = stack.pop();
            if ((c == ')' && sTop == '(') || (c == '}' && sTop == '{') || (c == ']' && sTop == '[')){
                continue;
            }
            return false;
        }
        return stack.empty();
    }
}
